1. Field of the Invention
This invention relates generally to methods and apparatus for converting electronically stored image data into a form which can be used to drive a dot matrix output device. More particularly, the present invention relates to an improved method and apparatus for implementing a scan-conversion theory used to provide shape filling of characters/graphics in spline outline formats in an efficient real time image processing system including dot matrix output devices such as cathode ray tubes and dot printing devices, where image data is converted from a graphical/mathematical format to a display or print device format (i.e. a series of dots/pixels).
2. Brief Description of the Prior Art
Two essential processes required to generate any two-dimensional shapes from the original outline formats are "scan-conversion" and "shape-filling". Scan-conversion is the process of selecting the pattern of device pixel dots which match the mathematical representation of the image outline to be displayed, while filling is the process of turning on device pixel dots which fall within the interior area bounded by the outline pixel dots generated from the scan-conversion process. In today's applications where the majority of the images require the use of filling, for example, typographic characters, most of the scan-conversion methods of the prior art do not optimize quality and performance. It is desirable that printed or displayed characters replicate the authentic design at an acceptable speed. While different typographic designers may choose different formats to store the type designs, such as vectors, arcs, Beziers, B-spline, etc., it is more desirable for a commercial product to use one general set of scan-conversion and filling methods to adapt various available font standards,, rather than to use several independent methods for different formats.
In an early study of this field, reported in a scientific article entitled "Algorithm for Computer Control of a Digital Plotter"by J. E. Bresenham (IBM Systems Journal, Vol. 4, No. 1, 1965), a scan-conversion method for filling character outline shapes generates darker, bolder shapes than the actual character designs and has a deleterious effect which is most visible at smaller point sizes and/or lower resolution raster devices where there is a constraint on the number of pixels available for each specific image. Bresenham's later study entitled "A Linear Algorithm for Incremental Digital Display of Circular Arcs" (Communication of the ACM, 20(2), February, 1977, pp. 100-106; see also Fundamentals of Interactive Computer Graphics by J. D. Foley and A. Van Dam, Addison-Wesley Publishing Co., 1982, pp. 433-436, 461), describes a scan-conversion concept which is specific to particular arc types. The study done on the filling methods was separate from the research on the scan-conversion processes, and, as a result, these independent findings can not be merged to offer a uniform, compatible solution.
U.S. Pat. No. 4,626,838 issued to Shigeo Tsujioka et al. on Dec. 2, 1986, entitled "Filled Shaped Generating Apparatus", discloses a technique employing interior filling and parity scan line filling concepts in a hardware module to perform the polygon fill function at a faster speed. In Tsujioka's design, a microprocessor is used to perform the Bresenham algorithm scan-conversion function. The polysegments generated by the microprocessor are fed to a hardware filling module, which comprises one "Filling Starting/Ending Point Generating Circuit", one "Filling Starting/Ending Point Memory", one "Contour Memory", and one "Filling Circuit". The result is an interior bitmap which is written to the "Refresh Memory" to be displayed on a cathode ray tube (CRT). In Tsujioka et al., the coordinate values representing the polysegments are in an integer form. The integer values are sent to the "Filling Starting/Ending Point Generating Circuit" to calculate the address of the Filling Starting Point and the address of the Filling Ending Point for every line segment in the polysegment. Because the coordinates are in the integer and not real number form, fine curve nature such as the serif of a character might be lost in the process. To fill the polygon interior and to paint the polygon contour, two separate memories, "Contour Memory" and "Filling Starting/Ending Point Memory", are used in the Tsujioka et al, method.
U.S. Pat. No. 4,745,575 issued to Adrian Hawes on May 17, 1988, entitled "Area Filling Hardware for a Color Graphics Frame Buffer", discloses a technique using hardware to accomplish area filling. A microprocessor is used to perform the Bresenham algorithm of scan-conversion. Polysegments generated by the scan-conversion microprocessor are fed to a hardware filling module. Hawes uses one single Auxiliary Memory to store the outline of a polygon area, and stores the Filling Starting Point and Filling Ending Point information for all the horizontal filling spans involved in the scan-converted polygons. Since the design is based on the integer Bresenham algorithm, it suffers the same quality problem as in the Tsujioka et al. method when it is applied to render outline fonts; but the Hawes design saves one set of memory.
A scientific paper entitled "Vertical Scan-Conversion for Filing Purposes" by R. D. Hersch (Proceeding Computer Graphics International 88, Geneva, Springer Verlag, 1988), reports on studies of scan-conversion methods and describes a method for solving the incompatibility issue of scan-conversion and filling approaches. Splines are subdivided into variable lengths of polysegments which have non-integer vertices. From intersections between the polysegments and scan lines, the algorithm determines two transition pixels for each horizontal span as the beginning and ending indicators. Each transition pixel indicates a color change, from black to white, or vice versa. Between the two transition pixels are interior pixels which are filled by applying a "parity scan line fill method". In order to calculate the intersection and locate the transition pixels, a time-consuming geometrical computation is performed. The higher the resolution, the more calculations are involved.
U.S. Pat. No. 4,937,761 issued to Christopher Hassett on Jun. 26, 1990, entitled "Method and Apparatus for Enhanced Speed Graphic Image Processing", discloses a technique for rendering outline fonts using hardware. In Hassett, after a line or curve is scan-converted ("discrete point conversion" in Hassett's terminology) to polysegments, the coordinate values representing the polysegment are encoded in real numbers. The fine nature of the line or curve is preserved since the polysegments are encoded in real numbers. In the Hassett method, the scan-converted polysegments are further transformed to the coordinate resolution of the target marking engine. Scaling up or down operations may be applied to the polysegments during the "transforming" process. Hassett uses a dithering technique to smooth the polyline segments which are further scan-converted during the "transforming" step. The final scan-converted and dithered polysegments are separated as a dithered image outline shape and a map of interior pixels to be filled, which are then combined for receipt by the raster operator. By keeping the fractional part of the scan-converted coordinate values, Hassett's method provides better precision in determining the outline point, filling starting point, and filling ending point. However, two separated memories are required to store the Outline Points and Filling Starting Point/Filling Ending Points. The final bitmap image is provided by combining the outline image and the filled image resulting from parity filling all the Starting Points/Ending Points. Since the object outline is generated by the conventional scan-conversion algorithm (Bresenham algorithm is used as the example), the dithering technique is used to improve the bitmap image quality in Hassett's approach.